package msb.class07;


import java.util.*;


/**
 * 题目见同名md
 * <p>
 * 解题思路
 * 创建2个堆
 * 一个堆是放获奖者
 * 一个堆是放候选者
 * <p>
 * 创建一个map
 * 主键是用户id
 * 值是客户
 * <p>
 * 每次操作时
 */
public class Code04_EveryStepShowBoss {

    /**
     * @param arr 客户id数组
     * @param op  客户行为数组 T表示购买 F表示退货
     * @param k   购买力最强的前k个客户
     * @return 你的老板要求你每一步都告诉他，当前购买力最强的前k个客户
     * 入参示例：
     * arr= [3,3,1,2,1,2,5]
     * op = [T,T,T,T,F,T,F]
     * k = 3
     */
    public static List<List<Integer>> topK(int[] arr, boolean[] op, int k) {
        CustomerHandler customerHandler = new CustomerHandler(k);
        return customerHandler.handler(arr, op);
    }


    public static class CustomerHandler {

        Map<Integer, Customer> map = new HashMap<>();
        //获奖者堆
        Heap<Customer> winHeap = new Heap<>(new WinComparator());
        //候选者堆
        Heap<Customer> canHeap = new Heap<>(new CanComparator());
        int limit;

        public CustomerHandler(int limit) {
            this.limit = limit;
        }


        public List<List<Integer>> handler(int[] arr, boolean[] op) {
            List<List<Integer>> list = new ArrayList<>();
            for (int i = 0; i < arr.length; i++) {
                handlerItem(arr[i], op[i], i);
                list.add(listWin());
            }
            return list;
        }


        private List<Integer> listWin() {
            List<Integer> listWin = new ArrayList<>();
            winHeap.list.forEach(e -> listWin.add(e.id));
            return listWin;
        }

        /**
         * 1. 无用户信息&&卖行为->直接返回
         * 2. 处理用户
         * 2.1 有用户 -> 处理购买力
         * 2.2 无用户 -> 新增用户 -> 处理购买力
         * 3. 购买力不足时从map剔除
         * <p>
         * 4. 堆处理
         * 4.1 两个区都不在
         * 4.1.1 购买力不足 -> 跳过 (无效判断，新数据&&有购买力 必定是ture)
         * 4.1.2 获奖区有位置 -> 进入获奖区
         * 4.1.3 获奖区没位置 -> 进入候选区
         * 4.2 在获奖区 -> 区域内处理（handlerHeap）
         * 4.3 在候选区 -> 区域内处理（handlerHeap）
         * <p>
         * 5 区域间交互
         *
         * @param index
         * @param isBuy
         * @param time
         */
        private void handlerItem(int index, boolean isBuy, int time) {
            // 1
            if (!map.containsKey(index) && !isBuy) {
                return;
            }
            // 2
            Customer customer = map.get(index);
            if (customer == null) {
                customer = new Customer(index);
                map.put(index, customer);
            }
            customer.buy += isBuy ? 1 : -1;

            // 3
            if (customer.buy == 0) {
                map.remove(index);
            }

            // 4
            if (!winHeap.contain(customer) && !canHeap.contain(customer)) {
                // 4.1
                customer.time = time;
                if (winHeap.size() < limit) {
                    winHeap.push(customer);
                } else {
                    canHeap.push(customer);
                }
            } else if (winHeap.contain(customer)) {
                // 4.2
                handlerHeap(winHeap, customer);
            } else {
                // 4.3
                handlerHeap(canHeap, customer);
            }

            // 5
            moveHeap(time);
        }

        /**
         * 区域内处理
         * 1. 当前购买力不足 -> 剔除
         * 2. 当前购买力足够 -> 重定位
         */
        private void handlerHeap(Heap<Customer> heap, Customer customer) {
            if (customer.buy == 0) {
                heap.remove(customer);
            } else {
                heap.resign(customer);
            }
        }

        /**
         * 区域间交互
         * 1. 获奖区有位置 && 候选区有数据 -> 候选区弹出数据进入获奖区
         * 2. 获奖区无位置 && 候选区有数据
         * 2.1 比较各自区域堆顶数据
         * 2.2 需要交换 -> 各自区域弹出并压入对方区域
         */
        private void moveHeap(int time) {
            if (winHeap.size() < limit && canHeap.size() > 0) {
                Customer customer = canHeap.pop();
                customer.time = time;
                winHeap.push(customer);
            } else if (winHeap.size() == limit && canHeap.size() > 0) {
                Customer winEnd = winHeap.peek();
                Customer canTop = canHeap.peek();
                if (canTop.buy > winEnd.buy) {
                    winHeap.pop();
                    canHeap.pop();
                    winEnd.time = time;
                    canTop.time = time;
                    winHeap.push(canTop);
                    canHeap.push(winEnd);
                }
            }
        }
    }

    public static class Customer {
        private int id;
        private int time;
        private int buy;

        public Customer(int id) {
            this.id = id;
        }
    }

    /**
     * 获奖者比较器，弹出者为从获奖区淘汰的人
     * 1. 数量小的在上方
     * 2. 数量相同的时间小的在上方
     * 3. 获奖者的时间为进入获奖区的时间
     */
    public static class WinComparator implements Comparator<Customer> {
        @Override
        public int compare(Customer o1, Customer o2) {
            return o1.buy == o2.buy ? o1.time - o2.time : o1.buy - o2.buy;
        }
    }

    /**
     * 候选者比较器，弹出者为晋升获奖者的人
     * 1. 数量大的在上方
     * 2. 数量相同的时间小的在上方
     * 3. 候选者的时间为进入候选区的时间
     */
    public static class CanComparator implements Comparator<Customer> {
        @Override
        public int compare(Customer o1, Customer o2) {
            return o1.buy == o2.buy ? o1.time - o2.time : o2.buy - o1.buy;
        }
    }


    //-----------


    // 为了测试
    public static class Data {
        public int[] arr;
        public boolean[] op;

        public Data(int[] a, boolean[] o) {
            arr = a;
            op = o;
        }
    }

    // 为了测试
    public static Data randomData(int maxValue, int maxLen) {
        int len = (int) (Math.random() * maxLen) + 1;
        int[] arr = new int[len];
        boolean[] op = new boolean[len];
        for (int i = 0; i < len; i++) {
            arr[i] = (int) (Math.random() * maxValue);
            op[i] = Math.random() < 0.5 ? true : false;
        }
        return new Data(arr, op);
    }

    // 为了测试
    public static boolean sameAnswer(List<List<Integer>> ans1, List<List<Integer>> ans2) {
        if (ans1.size() != ans2.size()) {
            System.out.println(ans1.size());
            System.out.println(ans1.size());
            return false;
        }
        for (int i = 0; i < ans1.size(); i++) {
            List<Integer> cur1 = ans1.get(i);
            List<Integer> cur2 = ans2.get(i);
            if (cur1.size() != cur2.size()) {
                System.out.println(cur1);
                System.out.println(cur2);
                return false;
            }
            cur1.sort((a, b) -> a - b);
            cur2.sort((a, b) -> a - b);
            for (int j = 0; j < cur1.size(); j++) {
                if (!cur1.get(j).equals(cur2.get(j))) {
                    System.out.println(cur1);
                    System.out.println(cur2);
                    return false;
                }
            }
        }
        return true;
    }

    public static List<Integer> getCurAns(ArrayList<Customer> daddy) {
        List<Integer> ans = new ArrayList<>();
        for (Customer c : daddy) {
            ans.add(c.id);
        }
        return ans;
    }

    public static void cleanZeroBuy(ArrayList<Customer> arr) {
        List<Customer> noZero = new ArrayList<Customer>();
        for (Customer c : arr) {
            if (c.buy != 0) {
                noZero.add(c);
            }
        }
        arr.clear();
        for (Customer c : noZero) {
            arr.add(c);
        }
    }

    public static void move(ArrayList<Customer> cands, ArrayList<Customer> daddy, int k, int time) {
        if (cands.isEmpty()) {
            return;
        }
        // 候选区不为空
        if (daddy.size() < k) {
            Customer c = cands.get(0);
            c.time = time;
            daddy.add(c);
            cands.remove(0);
        } else { // 等奖区满了，候选区有东西
            if (cands.get(0).buy > daddy.get(0).buy) {
                Customer oldDaddy = daddy.get(0);
                daddy.remove(0);
                Customer newDaddy = cands.get(0);
                cands.remove(0);
                newDaddy.time = time;
                oldDaddy.time = time;
                daddy.add(newDaddy);
                cands.add(oldDaddy);
            }
        }
    }

    // 干完所有的事，模拟，不优化
    public static List<List<Integer>> compare(int[] arr, boolean[] op, int k) {
        HashMap<Integer, Customer> map = new HashMap<>();
        ArrayList<Customer> cands = new ArrayList<>();
        ArrayList<Customer> daddy = new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            int id = arr[i];
            boolean buyOrRefund = op[i];
            if (!buyOrRefund && !map.containsKey(id)) {
                ans.add(getCurAns(daddy));
                continue;
            }
            // 没有发生：用户购买数为0并且又退货了
            // 用户之前购买数是0，此时买货事件
            // 用户之前购买数>0， 此时买货
            // 用户之前购买数>0, 此时退货
            if (!map.containsKey(id)) {
                map.put(id, new Customer(id));
            }
            // 买、卖
            Customer c = map.get(id);
            if (buyOrRefund) {
                c.buy++;
            } else {
                c.buy--;
            }
            if (c.buy == 0) {
                map.remove(id);
            }
            // c
            // 下面做
            if (!cands.contains(c) && !daddy.contains(c)) {
                if (daddy.size() < k) {
                    c.time = i;
                    daddy.add(c);
                } else {
                    c.time = i;
                    cands.add(c);
                }
            }
            cleanZeroBuy(cands);
            cleanZeroBuy(daddy);
            cands.sort(new CandidateComparator());
            daddy.sort(new DaddyComparator());
            move(cands, daddy, k, i);
            ans.add(getCurAns(daddy));
        }
        return ans;
    }

    public static class CandidateComparator implements Comparator<Customer> {

        @Override
        public int compare(Customer o1, Customer o2) {
            return o1.buy != o2.buy ? (o2.buy - o1.buy) : (o1.time - o2.time);
        }

    }

    public static class DaddyComparator implements Comparator<Customer> {

        @Override
        public int compare(Customer o1, Customer o2) {
            return o1.buy != o2.buy ? (o1.buy - o2.buy) : (o1.time - o2.time);
        }

    }

    public static void main(String[] args) {
        int maxValue = 10;
        int maxLen = 100;
        int maxK = 6;
        int testTimes = 100000;
        System.out.println("测试开始");
        for (int i = 0; i < testTimes; i++) {
            Data testData = randomData(maxValue, maxLen);
            int k = (int) (Math.random() * maxK) + 1;
            int[] arr = testData.arr;
            boolean[] op = testData.op;
            List<List<Integer>> ans1 = topK(arr, op, k);
            List<List<Integer>> ans2 = compare(arr, op, k);
            if (!sameAnswer(ans1, ans2)) {
                for (int j = 0; j < arr.length; j++) {
                    System.out.println(arr[j] + " , " + op[j]);
                }
                System.out.println(k);
                System.out.println(ans1);
                System.out.println(ans2);
                System.out.println("出错了！");
                break;
            }
        }
        System.out.println("测试结束");
    }
}
